class Solution
{
public:
    bool validateStackSequences(vector<int> &pushed, vector<int> &popped)
    {
        stack<int> st;
        int ed1 = 0, ed2 = 0;
        int sz = pushed.size();
        while (ed1 < popped.size())
        {
            st.push(pushed[ed1++]);
            while (st.size() && popped[ed2] == st.top())
            {
                st.pop();
                ++ed2;
            }
        }
        return st.empty();
    }
};